package com.xxwy.lintcode;

/**
 * @author xxwy
 * on 2018/10/8 0008
 * ------------------
 * 题目：求最值
 * Coin Change
 * 给出不同面额的硬币以及一个总金额.
 * 写一个方法来计算给出的总金额可以换取的最少的硬币数量.
 * 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.
 * ------------------------------------
 * 例子：
 * 给出 coins = [1, 2, 5], amount = 11
 * 返回 3 (11 = 5 + 5 + 1)
 * 给出 coins = [2], amount = 3
 * 返回 -1
 *
 */
public class Num669 {

    public int coinChange(int[] coins, int amount) {
        // write your code here
        int f[] = new int[amount + 1];
        int i, j;
        f[0] = 0;
        for (i = 1; i <= amount; ++i) {
            f[i] = -1;
            for (j = 0; j < coins.length; ++j) {
                if (i >= coins[j] && f[i - coins[j]] != -1) {
                    if (f[i] == -1 || f[i - coins[j]] + 1 < f[i]) {
                        f[i] = f[i - coins[j]] + 1;
                    }
                }
            }
        }
        return f[amount];

    }

}
